// https://leetcode.cn/problems/min-cost-climbing-stairs/description/

// 算法思路总结：
// 1. 使用动态规划记录到达每阶的最小成本
// 2. 每阶成本由前两阶推导而来
// 3. 选择从前一阶或前两阶过来的最小成本
// 4. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        int n = cost.size();
        vector<int> dp(n + 1);

        dp[0] = 0, dp[1] = 0;
        for (int i = 2 ; i <= n ; i++)
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

        return dp[n];
    }
};

int main()
{
    vector<int> v1 = {10,15,20}, v2 = {1,100,1,1,1,100,1,1,100,1};
    Solution sol;

    cout << sol.minCostClimbingStairs(v1) << endl;
    cout << sol.minCostClimbingStairs(v2) << endl;

    return 0;
}